<!--
 * @Author: liuxuanlong
 * @Date: 2020-08-22 16:05:50
 * @LastEditTime: 2020-08-25 13:51:50
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \algorithm\20200822.html
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>

    <script>
        /*
            给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
            你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
        */

        /**
         * @description: 时间复杂度:O(n²)   空间复杂度:O（1）
         * @param {type} 
         * @return {type} 
         */
        var f1 = function (nums, target) {
            for (let i = 0; i < nums.length; i++) {
                for (let j = i + 1; j < nums.length; j++) {
                    if (nums[j] === target - nums[i]) {
                        return [i, j]
                    }
                }
            }
            return [-1, -1]
        }
        /**
         * @description: 时间复杂度:O(n²)   空间复杂度:O（n）
         *              使用map，map.get的时间复杂度为O(1)
         * @param {type} 
         * @return {type} 
         */
        var f2 = function (nums, target) {
            let map = new Map()
            for (let i = 0; i < nums.length; i++) {
                map.set(nums[i], i)
            }
            for (let i of nums) {
                if (map.has(target - i)) {
                    return [map.get(i), map.get(target - i)]
                }
            }
            return [-1, -1]
        }
        /**
         * @description: 时间复杂度:O(n²)   空间复杂度:O（n）
         *               相对于f2来说只进行一次循环
         * @param {type} 
         * @return {type} 
         */
        var f3 = function (nums, target) {
            let map = new Map()
            for (let i = 0; i < nums.length; i++) {

                if (map.has(target - nums[i])) {
                    return [i, map.get(target - nums[i])]
                } else {
                    map.set(nums[i], i)
                }
            }
            return [-1, -1]
        }

        /**
         * @description: 时间复杂度:O(nlogn)   空间复杂度:O（n）
         *               先排序然后用双指针条调整下标
         * @param {type} 
         * @return {type} 
         */

        var f4 = function (nums, target) {
            let arr = nums.concat();
            let arrTmp = qurkSort(arr);
            let i = 0
            let j = nums.length - 1
            while (i < j) {
                if (arrTmp[i] + arrTmp[j] > target) {
                    j--;
                } else if (arrTmp[i] + arrTmp[j] < target) {
                    i++;
                } else {
                    break
                }
            }
            let positionArr = []
            if (i < j) {
                for (let key = 0; key < nums.length; key++) {
                    if (i < nums.length && arrTmp[i] == nums[key]) {
                        positionArr.push(key)
                        i = -1
                    } else if (j < nums.length && arrTmp[j] == nums[key]) {
                        positionArr.push(key)
                        j = -1
                    }
                    if (i == -1 && j == -1) {
                        return positionArr
                    }
                }
            } else {
                return [-1, 1]
            }
        }
        var qurkSort = function (arr) {
            if (arr.length <= 1) {
                return arr;
            } else {
                var pivotIndex = Math.floor(arr.length / 2);
                var pivot = arr.splice(pivotIndex, 1)[0];
                var left = [];
                var right = [];
                for (let i = 0; i < arr.length; i++) {
                    if (arr[i] < pivot) {
                        left.push(arr[i])
                    } else {
                        right.push(arr[i])
                    }
                }
                return qurkSort(left).concat([pivot], qurkSort(right))
            }
        }

        let nums = [1, 2, 3, 7, 1, 4, 8];
        let target = 15;
        console.log(f1(nums, target))
        console.log(f2(nums, target))
        console.log(f3(nums, target))
        console.log(f4(nums, target))

    </script>
</body>

</html>